As described in U.S. Pat. 4,908,038 to Matsumura et al., cryptographic devices can be attacked using information gathered by observing the timing of comparison operations performed by such devices during their operation. For example, if a MAC (Message Authentication Code) algorithm is strong and the key is secure, forging a MAC should require O(2 n) attempts (where n is the MAC length in bits), but a device using a vulnerable MAC validation process is vulnerable to an O(n) timing attack.
If timing is the only source of leaked information, securing the device is often relatively straightforward. Previously known countermeasures to attacks involving information leaking from cryptosystems employ large and often expensive physical shielding and/or careful filtering of inputs and outputs (e.g., U.S. government Tempest specifications). Unfortunately, these techniques are difficult to apply in constrained engineering environments. For example, physical constraints (such as size and weight), cost, and the need to conserve power can often prevent the use of such techniques. It is also known to use certain computational techniques (e.g., see Matsumura, above, or P. Kocher, "Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems," Advances in Cryptology--CRYPTO '96, Springer-Verlag, 1996, pages 104-113) to equalize timing. However, sources of information leakage other than timing (e.g., a device's power consumption) provide other avenues of attack. Indeed, Matsumara's timing equalization system itself can be vulnerable to non-timing attacks, for example by analyzing power consumption to detect the start of processing delays. It would therefore be advantageous to protect the devices' internal operations themselves instead of (or in addition to) simply externally masking the devices' timing (or other) fluctuations.
The present invention includes countermeasures that can be incorporated into software and/or hardware, to provide improved protection at relatively low cost. Thus, the invention could be used in place of (or in addition to) traditional countermeasures. For example, the present invention can be implemented in smartcards and other highly constrained environments where physical shielding and other protection measures cannot be readily applied.